package bin_tree;

import java.util.NoSuchElementException;

public class BST {
    private class TreeNode{
        private int val;
        private TreeNode left;
        private TreeNode right;

        public TreeNode(int val) {
            this.val = val;

        }
    }
    private int size;//当前节点个数
    private TreeNode root;//根节点
    public void add(int val){
        root=add(root,val);
    }

    private TreeNode add(TreeNode root, int val) {
        TreeNode newNode=new TreeNode(val);
        if(root==null){
            //当前插入值就是根节点
            size++;
            return newNode;
        }
        if(val<root.val){
            //左树插入
            root.left=add(root.left,val);
        }
        if(val> root.val){
            root.right=add(root.right,val);
        }
        return root;
    }

    @Override
    public String toString() {
        StringBuilder sb=new StringBuilder();
        //先序遍历打印
        generateBSTString(root,0,sb);
        return sb.toString();
    }

    private void generateBSTString(TreeNode root, int height, StringBuilder sb) {
        //边界
        if(root==null){
            sb.append(generateBSTString(height)).append("NULL\n");
            return;
        }
        //先打印根节点
        sb.append(generateBSTString(height)).append(root.val).append("\n");
        //递归访问左子树
        generateBSTString(root.left,height+1,sb);
        //递归访问右子树
        generateBSTString(root.right,height+1,sb);
    }

    private String generateBSTString(int height) {
        //打印“--”，每多一层就多两个“--”
        StringBuilder sb=new StringBuilder();
        for (int i = 0; i < height; i++) {
            sb.append("--");
        }
        return sb.toString();
    }
    public int findMin(){
        if(size==0){
            //空树
            throw new NoSuchElementException("BST is empty!cannot find min");
        }
        TreeNode minNode=minNode(root);
        return minNode.val;
    }

    private TreeNode minNode(TreeNode root) {
        if(root.left==null){
            //此时root就是最小值
            return root;
        }
        return minNode(root.left);
    }
    public int findMax(){
        if(size==0){
            throw new NoSuchElementException("BST is empty!cannot find max");

        }
        TreeNode maxNode=maxNode(root);
        return maxNode.val;
    }

    private TreeNode maxNode(TreeNode root) {
        if(root.right==null){
            return root;
        }
        return maxNode(root.right);
    }
    public int removeMin(){
        int min=findMin();//找到最小值
        root=removeMin(root);//删除最小值
        return min;
    }

    private TreeNode removeMin(TreeNode root) {
        if(root.left==null){
            //当前节点就是最小值节点，待删除
            TreeNode right=root.right;
            root=root.right=null;
            size--;
            return right;
        }
        //不是最小值，递归去左子树中删除
        root.left=removeMin(root.left);
        return root;
    }
    public int removeMax(){
        int max=findMax();
        root=removeMax(root);
        return max;
    }

    private TreeNode removeMax(TreeNode root) {
        if(root.right==null){
            //此节点是待删除节点
            TreeNode left=root.left;
            root=root.left=null;
            size--;
            return left;
        }
        //此时右子树不为空，继续在右子树中找待删除的最大值
        root.right=removeMax(root.right);
        return root;
    }
    public void remove(int val){
        root=remove(root,val);
    }

    private TreeNode remove(TreeNode root, int val) {
        if(root==null){
            throw new NoSuchElementException("BST中没有值为"+val+"的节点");
        }else if(val<root.val){
            //左子树中找待删除节点
            root.left=remove(root.left,val);
            return root;
        }else if(val>root.val){
            //右子树中找待删除节点
            root.right=remove(root.right,val);
            return root;
        }else{
            //当前节点就是待删除结点
            if(root.left==null){
                //只有右孩子，返回右孩子即可（和删除最小值一样）
                TreeNode right=root.right;
                root=root.right=null;
                size--;
                return right;
            }
            if(root.right==null){
                //右子树为空，只有左孩子（跟删除最大值一样）
                TreeNode left=root.left;
                root.left=root=null;
                size--;
                return left;
            }
            //此时，左右孩子都不为空，找前驱或者后继，这里找后继
            TreeNode successor=minNode(root.right);//右子树中最小的节点就是那个后继
            successor.right=removeMin(root.right);//原先后继所在位置删了
            successor.left=root.left;
            root.left=root.right=root=null;
            return successor;
        }
    }

    public static void main(String[] args) {

//                int[] data={28,16,30,13,22,29,42};
        int[] data={41,58,50,60,42,53,59,63};
                BST bst=new BST();
                for(int i:data){
                    bst.add(i);
                }

//        System.out.println(bst.removeMax());
//        System.out.println(bst.removeMin());
        bst.remove(58);
        System.out.println(bst);
    }
}
